package ExerDemo;

/**
 * @Author 不知名网友鑫
 * @Date 2022/5/7
 * labulangdong算法笔记——二分
 **/
public class BinarySearchs {
    public static void main(String[] args) {
        int [] nums={1,3,5,7,9,10,11,12};
        //二分查找
        System.out.println(BinarySearch(nums,3));
        //搜索左侧边界，返回2表示数组中有两个数小于4。
        System.out.println(left_BinarySearch(nums,4));
    }
    //最朴素的二分搜索。
    public static int BinarySearch(int [] nums,int target){
        //首先明确：退出while循环，就表明当前区间没有需要找的target。
        //1. 为什么要将right=nums.length-1，left<=right？
        //此时搜索的区间为[left,right]，如果退出while循环,left==right+1,此时的区间为[right+1，right]，明显地，区间中没有数字，表示我们全部搜索到了。

        //2. 为什么也可以是right=nums.length,left<right?
        //此时的搜索区间为[left,right)，如果退出while循环，left==right，此时的区间为[right,right),区间内还有数字，此时的left/right没有被搜索。
        //但是要注意，退出要加上一个判断条件，nums[left]==target ? left:-1。

        int left=0,right=nums.length-1;
        int mid=0;
        while(left<=right){
            //为了防止left+right太大导致溢出,所以使用left+(right-left)/2
            mid = left+(right-left)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]<target){
                left = mid+1;
            } else if (nums[mid]>target) {
                right = mid-1;
            }
        }
        return -1;
        }
    //寻找左侧边界的二分搜索。
    public static int left_BinarySearch(int []nums,int target){
        int left=0,right=nums.length-1;
        int mid=0;
        while(left<=right){
            mid = left+(right-left)/2;
            if(nums[mid]==target){
                //收缩右侧边界，不断向左靠拢
                right=mid-1;
            }else if(nums[mid]<target){
                left= mid+1;
            }else if(nums[mid]>target){
                right = mid-1;
            }
        }
        //如果想和上面的代码统一，也可以使用这种方式
        //       出界         ||  没找到target
//        if(left>=nums.length || nums[left]!=target){
//            return -1;
//        }
        return left;
    }
    //搜索右侧边界的二分搜索
    public static int right_BinarySearch(int []nums,int target){
        int left=0,right=nums.length-1;
        int mid=0;
        while(left<=right){
            mid = left+(right-left)/2;
            if(nums[mid]==target){
                //收缩左侧边界，不断向右靠拢
                left=mid+1;
            }else if(nums[mid]<target){
                left= mid+1;
            }else if(nums[mid]>target){
                right = mid-1;
            }
        }
        //如果想和上面的代码统一，也可以使用这种方式
        //       出界         ||  没找到target
//        if(right<0 || nums[right]!=target){
//            return -1;
//        }

        //因为在收缩左侧边界时，left=mid+1了，
        // 所以此时的nums[left]一定不等于target了，nums[left-1]可能等于target。
        return left-1;
    }
}

